<html><head>

<meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<meta name="Generator" content="Microsoft Word 73.1"><title>Happy Numbers</title></head><body>

<font size="4"></font><p align="center"><b><font size="4">Happy Numbers</font></b></p>
<font face="Times"><p> </p>
<b><p>Background</p>
</b><p> </p>
</font><p align="justify">Let the sum of the squares of the digits of a positive integer s<sub>0</sub> be represented by s<sub>1</sub>. In a similar way, let the sum of the squares of the digits of s<sub>1</sub> be represented by s<sub>2</sub>, and so on. If s<sub>i</sub>=1 for some i&gt;=1, then the original integer s<sub>0</sub> is said to be <b>happy</b>. For example, starting with 7 gives the sequence </p>
<p>	<b>7</b>, <b>49</b> (=7^2), <b>97</b> (=4^2+9^2), <b>130</b> (=9^2+7^2), <b>10</b> (=1^2+3^2), <b>1</b> (=1^2), </p>
<p>so 7 is a happy number. </p>
<p align="justify">The first few happy numbers are 1, 7, 10, 13, 19,
23, 28, 31, 32, 44, 49, 68, 70, 79, 82, 86, 91, 94, 97, 100, .... The
number of iterations i required for these to reach 1 are, respectively,
1, 6, 2, 3, 5, 4, 4, 3, 4, 5, 5, 3, .... </p>
<p align="justify">A number that is not happy is called <b>unhappy</b>. Once it is known whether a number is happy (unhappy), then any number in the sequence s<sub>1</sub>, s<sub>2</sub>, s<sub>3</sub>, ... will also be happy (unhappy). Unhappy numbers have eventually periodic sequences of s<sub>i</sub> which do not reach 1 (e.g., 4, 16, 37, 58, 89, 145, 42, 20, 4, ...). </p>
<p align="justify">Any permutation of the digits of a happy (unhappy)
number must also be happy (unhappy). This follows from the fact that
addition is commutative. Moreover, the product of a happy (unhappy)
number by any power of ten is a happy (unhappy) number. Example: 58 is
an unhappy number; then, so are 85, 580, 850, 508, 805, 5800, 5080,
5008, 8050, 8500, and so on.</p>
<b><font face="Times"></font></b><p><b><font face="Times"> </font></b></p>
<p><b><font face="Times">Problem</font></b></p>
<p>Decide which numbers, in a given closed interval, are happy numbers.</p>
<b><font face="Times"></font></b><p><b><font face="Times"> </font></b></p>
<p><b><font face="Times">Input</font></b></p>
<p align="justify">The input has <b>n</b> lines each of them corresponding to a test case. Every line contains two positive
integers between 1 and 99999 (inclusive) each; the first integer, L, is the low
limit of the closed interval; the second one, H, is the high limit (L &#8804; H).  </p>
<b><font face="Times"></font></b><p><b><font face="Times"> </font></b></p>
<p><b><font face="Times">Output</font></b></p>
<p align="justify">The output is composed of the happy numbers that lie
in the interval [L,H], together with the number of iterations required
for the corresponding sequences of squares to reach 1. </p>
<p align="justify">There must be a line for each happy number
containing the happy number followed by a space and the number of
iterations required for the sequence of squares to reach 1.</p>
<p align="justify">Print a blank line between two consecutive test cases.</p>
<b><font face="Times"></font></b><p><b><font face="Times"> </font></b></p>
<p><b><font face="Times">Sample Input</font></b></p>
<pre><font face="Times">5 28
233 250
</font></pre>

<font face="Times"><b><font face="Times"></font></b></font><p><font face="Times"><b><font face="Times">Sample Output</font></b></font></p>
<pre><font face="Times"><font face="Times">7 6
10 2
13 3
19 5
23 4
28 4

236 6
239 6
</font></font></pre>

<p></p>
<font face="Times"><font face="Times"><i><p>The definition of happy numbers is from MathWorld - http://mathworld.wolfram.com/</p></i></font>
</font></body></html>